package leetcode;

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}

/**
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * 
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * 
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 
 * 示例：
 * 
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
 * 
 */
public class Solution {
	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode l3 = new ListNode(0); ListNode prev = l3;

	    while (l1 != null && l2 != null){
	        int val = l1.val + l2.val;
	        if(val > 9){
	            prev.val += 1;
	        }
	        l1 = l1.next;
	        l2 = l2.next;
	        ListNode ld = new ListNode(val > 9 ? val-10 : val);
	        prev.next = ld;
	        prev = prev.next;
	    }

	    return l3.next;
	}
	
	/**
	 * 判断丑数  只包含质因数 2, 3, 5 的正整数。
	 * @param num
	 * @return
	 */
	public static boolean isUgly(int num) {
		
		while(num!=1){
            int t=num;
            if(num%2==0)num/=2;
            if(num%3==0)num/=3;
            if(num%5==0)num/=5;
            if(t==num)return false;//如果一趟下来num的值没变，则num无法被2,3,5整除
        }
        return true;

	}
	
	public static int[] plusOne(int[] digits) {
        
        int addstep=0;
        for (int i = digits.length-1; i >=0; i--) {
        	if(i==digits.length-1){
        		int sum=digits[i]+1;
        		if(sum>=10){
        			addstep=sum/10;
        			digits[i]=sum%10;
        		}else{
        			digits[i]=sum%10;
        			addstep=0;
        		}
        	}else{
        		int sum=digits[i]+addstep;
        		if(sum>=10){
        			addstep=sum/10;
        			digits[i]=sum%10;
        		}else{
        			digits[i]=sum%10;
        			addstep=0;
        		}
        	}
		}
        if(addstep>0){
        	//需要数组扩容
        	int[] temp=new int[digits.length+1];
        	temp[0]=addstep;
        	for (int i = 1; i < temp.length; i++) {
				temp[i]=digits[i-1];
			}
        	return temp;
        }
        return digits;
    }

	public static void main(String[] args) {
//		ListNode l1 = new ListNode(2);
//		ListNode l3 = new ListNode(4);
//		ListNode l5 = new ListNode(3);
//		l1.next = l3;
//		l3.next = l5;
//
//		ListNode l2 = new ListNode(5);
//		ListNode l4 = new ListNode(6);
//		ListNode l6 = new ListNode(4);
//		l2.next = l4;
//		l4.next = l6;
//
//		ListNode addTwoNumbers = addTwoNumbers(l1, l2);
//		System.out.println(addTwoNumbers.val + "--" + addTwoNumbers.next.val + "--" + addTwoNumbers.next.next.val);
		
		System.out.println(isUgly(2));
		int [] nums={9,9,9};
		int[] plusOne = plusOne(nums);
		for (int i : plusOne) {
			System.out.println(i);
		}
		System.out.println();
	}
}